#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_STACK_SIZE 100  // 遍历栈最大深度
#define MAX_DOT_LEN 10240   // DOT字符串最大长度

// ========================= 动态数组（模拟Python list） =========================
typedef struct {
    void** data;
    int size;
    int capacity;
} DynamicArray;

// 初始化动态数组
DynamicArray* da_init(int init_capacity) {
    DynamicArray* da = (DynamicArray*)malloc(sizeof(DynamicArray));
    if (!da) return NULL;
    da->capacity = init_capacity > 0 ? init_capacity : 4;
    da->data = (void**)malloc(da->capacity * sizeof(void*));
    da->size = 0;
    return da;
}

// 动态数组扩容
static bool da_resize(DynamicArray* da) {
    if (!da) return false;
    int new_cap = da->capacity * 2;
    void** new_data = (void**)realloc(da->data, new_cap * sizeof(void*));
    if (!new_data) return false;
    da->data = new_data;
    da->capacity = new_cap;
    return true;
}

// 向动态数组尾部添加元素
bool da_add(DynamicArray* da, void* elem) {
    if (!da) return false;
    if (da->size >= da->capacity && !da_resize(da)) {
        fprintf(stderr, "动态数组扩容失败\n");
        return false;
    }
    da->data[da->size++] = elem;
    return true;
}

// 向动态数组指定索引插入元素
bool da_insert(DynamicArray* da, int index, void* elem) {
    if (!da || index < 0 || index > da->size) return false;
    if (da->size >= da->capacity && !da_resize(da)) {
        fprintf(stderr, "动态数组扩容失败\n");
        return false;
    }
    // 移动后续元素
    memmove(&da->data[index + 1], &da->data[index], (da->size - index) * sizeof(void*));
    da->data[index] = elem;
    da->size++;
    return true;
}

// 获取动态数组指定索引元素
void* da_get(const DynamicArray* da, int index) {
    if (!da || index < 0 || index >= da->size) return NULL;
    return da->data[index];
}

// 释放动态数组（可选释放元素）
void da_destroy(DynamicArray* da, void (*free_elem)(void*)) {
    if (!da) return;
    if (free_elem) {
        for (int i = 0; i < da->size; i++) {
            free_elem(da->data[i]);
        }
    }
    free(da->data);
    free(da);
}

// ========================= 节点结构体（模拟Python Node类） =========================
typedef struct Node Node;

struct Node {
    int value;               // 节点值
    Node* parent;            // 父节点
    DynamicArray* children;  // 子节点列表（DynamicArray<Node*>）
};

// 创建节点
Node* node_create(int value) {
    Node* node = (Node*)malloc(sizeof(Node));
    if (!node) return NULL;
    node->value = value;
    node->parent = NULL;
    node->children = da_init(4);
    if (!node->children) {
        free(node);
        return NULL;
    }
    return node;
}

// 释放节点（递归释放所有子节点）
void node_destroy(Node* node) {
    if (!node) return;
    // 递归释放子节点
    for (int i = 0; i < node->children->size; i++) {
        Node* child = (Node*)da_get(node->children, i);
        node_destroy(child);
    }
    da_destroy(node->children, NULL);  // 子节点已手动释放
    free(node);
}

// 查找父节点和兄弟节点（对应Python Node.find_parent）
void node_find_parent(Node* start_node, int e, Node** out_p, Node** out_sib) {
    Node* x = start_node;
    Node* prev = x;
    while (x != NULL && x->value >= e) {
        prev = x;
        x = x->parent;
    }
    *out_p = x;
    *out_sib = prev;
}

// ========================= 置换树结构体（模拟Python Tree类） =========================
typedef struct {
    Node* root;  // 根节点（value=0）
} Tree;

// 初始化置换树
Tree* tree_create() {
    Tree* tree = (Tree*)malloc(sizeof(Tree));
    if (!tree) return NULL;
    tree->root = node_create(0);  // 根节点固定值为0
    if (!tree->root) {
        free(tree);
        return NULL;
    }
    return tree;
}

// 释放置换树
void tree_destroy(Tree* tree) {
    if (!tree) return;
    node_destroy(tree->root);
    free(tree);
}

// 查找子节点列表中插入位置（对应Python Tree.index_of）
int tree_index_of(const DynamicArray* children, int e) {
    if (!children || children->size == 0) return 0;
    int start = 0;
    int end = children->size - 1;
    while (start != end) {
        int mid = (start + end) / 2;
        Node* mid_node = (Node*)da_get(children, mid);
        if (e < mid_node->value) {
            end = mid;
        } else if (e == mid_node->value) {
            return mid;
        } else {
            start = mid + 1;  // 原Python逻辑修复：避免死循环
        }
    }
    // 最终判断start位置的节点值，确定插入位置
    Node* start_node = (Node*)da_get(children, start);
    return (e < start_node->value) ? start : start + 1;
}

// 构建置换树（对应Python Tree.of）
bool tree_build(Tree* tree, const int* array, int len) {
    if (!tree || !array || len <= 0) return false;

    // 存储节点映射（value -> Node*），避免重复创建
    Node** node_map = (Node**)calloc(len + 1, sizeof(Node*));  // 假设value不超过len（可按需调整）
    if (!node_map) return false;

    for (int i = 0; i < len; i++) {
        int e = array[i];
        Node* node = node_create(e);
        if (!node) {
            // 释放已创建的节点
            for (int j = 0; j < i; j++) {
                node_destroy(node_map[array[j]]);
            }
            free(node_map);
            return false;
        }
        node_map[e] = node;

        if (i == 0) {
            // 第一个元素直接作为根节点的子节点
            da_add(tree->root->children, node);
            node->parent = tree->root;
        } else {
            int prev_e = array[i - 1];
            Node* prev_node = node_map[prev_e];
            if (e > prev_e) {
                // e > 前一个元素：作为前一个节点的子节点
                da_add(prev_node->children, node);
                node->parent = prev_node;
            } else {
                // e <= 前一个元素：查找父节点和兄弟节点，插入到父节点的子节点列表
                Node *p, *sib;
                node_find_parent(prev_node, e, &p, &sib);
                if (!p) p = tree->root;  // 找不到父节点时，父节点为根
                // 查找插入位置
                int insert_idx = tree_index_of(p->children, e);
                da_insert(p->children, insert_idx, node);
                node->parent = p;
            }
        }
    }

    free(node_map);
    return true;
}

// 生成DOT字符串（对应Python Tree.to_dot_string）
char* tree_to_dot_string(const Tree* tree) {
    if (!tree || !tree->root) return NULL;

    char* dot = (char*)malloc(MAX_DOT_LEN);
    if (!dot) return NULL;
    memset(dot, 0, MAX_DOT_LEN);

    // 初始化DOT头部
    strcat(dot, "digraph {\n");
    // 根节点
    char buf[100];
    snprintf(buf, sizeof(buf), "\tn%d[label=\"%d\"]\n", tree->root->value, tree->root->value);
    strcat(dot, buf);

    // 栈实现DFS遍历（后序入栈，保证输出顺序与Python一致）
    Node* stack[MAX_STACK_SIZE];
    int stack_top = 0;
    stack[stack_top++] = tree->root;

    while (stack_top > 0) {
        Node* v = stack[--stack_top];

        // 子节点逆序入栈（保证遍历顺序与Python一致）
        for (int i = v->children->size - 1; i >= 0; i--) {
            Node* child = (Node*)da_get(v->children, i);
            stack[stack_top++] = child;

            // 生成子节点和边的DOT代码
            snprintf(buf, sizeof(buf), "\tn%d[label=\"%d\"]\n", child->value, child->value);
            strcat(dot, buf);
            snprintf(buf, sizeof(buf), "\tn%d -> n%d\n", v->value, child->value);
            strcat(dot, buf);
        }
    }

    strcat(dot, "}\n");
    return dot;
}

// 转换为排列（对应Python Tree.to_permutation）
int* tree_to_permutation(const Tree* tree, int* out_len) {
    if (!tree || !tree->root || !out_len) return NULL;

    // 第一步：统计非根节点数量（排列长度）
    int count = 0;
    Node* stack_count[MAX_STACK_SIZE];
    int stack_top = 0;
    stack_count[stack_top++] = tree->root;

    while (stack_top > 0) {
        Node* v = stack_count[--stack_top];
        if (v->value != 0) count++;
        // 逆序入栈，保证统计顺序不影响计数
        for (int i = v->children->size - 1; i >= 0; i--) {
            stack_count[stack_top++] = (Node*)da_get(v->children, i);
        }
    }

    *out_len = count;
    int* perm = (int*)malloc(count * sizeof(int));
    if (!perm) return NULL;

    // 第二步：DFS遍历生成排列（与Python栈遍历逻辑一致）
    int idx = 0;
    Node* stack_perm[MAX_STACK_SIZE];
    stack_top = 0;
    stack_perm[stack_top++] = tree->root;

    while (stack_top > 0) {
        Node* v = stack_perm[--stack_top];
        if (v->value != 0) {
            perm[idx++] = v->value;
        }
        // 子节点正序入栈（保证输出顺序与Python一致）
        for (int i = 0; i < v->children->size; i++) {
            stack_perm[stack_top++] = (Node*)da_get(v->children, i);
        }
    }

    return perm;
}

// ========================= 测试代码 =========================
int main() {
    // 测试数组：[3,4,2,1]（与Python一致）
    int array[] = {3, 4, 2, 1};
    int len = sizeof(array) / sizeof(array[0]);

    // 1. 创建并构建置换树
    Tree* tree = tree_create();
    if (!tree || !tree_build(tree, array, len)) {
        fprintf(stderr, "置换树构建失败\n");
        return 1;
    }

    // 2. 生成DOT字符串并打印
    char* dot_str = tree_to_dot_string(tree);
    if (dot_str) {
        printf("DOT字符串：\n%s", dot_str);
        free(dot_str);
    }

    // 3. 转换为排列并打印
    int perm_len = 0;
    int* perm = tree_to_permutation(tree, &perm_len);
    if (perm) {
        printf("置换树转换为排列：");
        printf("[");
        for (int i = 0; i < perm_len; i++) {
            printf("%d", perm[i]);
            if (i != perm_len - 1) {
                printf(", ");
            }
        }
        printf("]\n");
        free(perm);
    }

    // 4. 释放资源
    tree_destroy(tree);

    return 0;
}